package linear;

public class CopyLinkedListWithRandPtr138 {
    static class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
    public static Node copyRandomList(Node head) {
        Node cur = head;
        if(head == null)
            return head;
        while(cur != null){
            Node copy = new Node(cur.val);
            Node next = cur.next;
            cur.next = copy;
            copy.next = next;
            cur = copy.next;
        }
        Node pointer = head;
        while(pointer != null){
            pointer.next.random = pointer.random.next;
            pointer = pointer.next.next;
        }
        Node copyHead = head.next;
        Node copyCur = copyHead;
        while(copyCur != null){
            copyCur.next = copyCur.next.next;
            copyCur = copyCur.next;
        }
        copyCur.next = null;
        return copyHead;

    }
}
